package exampleQuestions;

public class DiameterOfATree {

	static class Node {

		int val;
		Node left, right;

		public Node(int v) {
			this.val = v;
		}

	}

	/**
	 * Find the Diameter of the tree.
	 * 
	 * Find algorithm !!!
	 */
	public static void main(String[] args) {

		Node root = new Node(6);

		Node n1 = new Node(5);
		Node n2 = new Node(4);
		Node n3 = new Node(3);
		Node n4 = new Node(2);
		Node n5 = new Node(0);

		Node n6 = new Node(8);
		Node n7 = new Node(9);
		Node n8 = new Node(14);

		root.left = n3;
		root.right = n7;

		n7.right = n8;
		n7.left = n6;

		n3.left = n5;
		n5.right = n4;
		n3.right = n1;

		n1.right = n2;
		Node n10 = new Node(11);
		Node n11 = new Node(-5);
		Node n12 = new Node(-3);
		Node n13 = new Node(22);
		n2.left = n10;
		n4.left = n11;
		n11.right = n12;
		n8.right = n13;

		System.out.println(getDiameter(root));

		// System.out.println(getHeight(root.left));
		// System.out.println(getHeight(root.right));
		System.out.println(getHeight(n3));

	}

	private static int getDiameter(Node root) {
		if (root != null) {
			return Math.max(getDiameter(root.left), Math.max(
					getHeight(root.left) + getHeight(root.right),
					getDiameter(root.right)));
		} else {
			return 0;
		}

	}

	private static int getHeight(Node n) {
		if (n == null) {
			return 0;
		} else
			return 1 + Math.max(getHeight(n.left), getHeight(n.right));
	}

}
